import com.sun.source.tree.Tree;

import java.util.ArrayDeque;
import java.util.ArrayList;
import java.util.List;
import java.util.Queue;

public class BinarySearchTree {
    static class TreeNode {
        public int val;
        public TreeNode left;
        public TreeNode right;

        public TreeNode(int val) {
            this.val = val;
        }
    }

    public TreeNode root;//根节点

    //向树中插入一个节点
    public void insert(int k) {
        if (root == null) {
            root = new TreeNode(k);
            return;
        }
        TreeNode cur = root;
        TreeNode parent = null;
        TreeNode node = new TreeNode(k);
        while (cur != null) {
            if (node.val < root.val) {
                parent = cur;
                cur = cur.left;
            } else if (node.val > root.val) {
                parent = cur;
                cur = cur.right;
            } else {
                //不能插入两个相同的数据
                return;
            }
        }
        if (node.val < parent.val) {
            parent.left = node;
        } else {
            parent.right = node;
        }
    }

    //查询某个节点
    public TreeNode search(int key) {
        TreeNode cur = root;
        while (cur != null) {
            if (cur.val < key) {
                cur = cur.right;
            } else if (key == cur.val) {
                return cur;
            } else {
                cur = cur.left;
            }
        }
        return null;
    }

    //删除某个节点
    public void remove(int key) {
        TreeNode cur = root;
        TreeNode parent = null;
        //找到cur节点和cur的parent的节点
        while (cur != null) {
            if (key > cur.val) {
                parent = cur;
                cur = cur.right;
            } else if (key < cur.val) {
                parent = cur;
                cur = cur.left;
            } else {
                removeNode(cur, parent);
            }
        }
    }

    public void removeNode(TreeNode cur, TreeNode parent) {
        if (cur.left == null) {
            if (cur == root) {
                root = cur.right;
            } else if (parent.left == cur) {
                parent.left = cur.right;
            } else {
                parent.right = cur.right;
            }
        } else if (cur.right == null) {
            if (cur == root) {
                root = cur.left;
            } else if (parent.left == cur) {
                parent.left = cur.left;
            } else {
                parent.left = cur.left;
            }
        } else {
            TreeNode t = cur.left;
            TreeNode tp = cur;
            while (t.right != null) {
                tp = t;
                t = t.right;
            }
            cur.val = t.val;
            if (tp.left == t) {
                tp.left = t.left;
            } else {
                tp.right = t.left;
            }
        }
    }

    //判断两颗二叉树树是否相同
    public boolean isSameTree(TreeNode p, TreeNode q) {
        if (p == null && q == null) {
            return true;
        } else if (p == null && q != null || p != null && q == null) {
            return false;
        } else if (p.val != q.val) {
            return false;
        }
        return isSameTree(p.left, q.left) && isSameTree(p.right, q.right);
    }

    //判断一棵树是否包含了另一颗树
    public boolean isSubtree(TreeNode root, TreeNode subRoot) {
        if (subRoot == null) {
            return true;
        } else if (root == null) {
            return false;
        }
        //这里比较root树和subRoot树是否相同，然后再递归root左数和右树
        return isSubtree(root.left, subRoot) || isSubtree(root.right, subRoot) || isSameTree(root, subRoot);//只要返回一个true 说明就包含了
    }

    //倒转一棵二叉树
    public TreeNode invertTree(TreeNode root) {
        if (root == null) {
            return root;
        }
        //交换每个节点的左子树和右子树
        TreeNode node = root.left;
        root.left = root.right;
        root.right = node;
        //继续往下遍历
        invertTree(root.left);
        invertTree(root.right);
        return root;
    }

    //判断一棵二叉树是否是对称二叉树
    //先写一个比较两棵二叉树是否对称的函数
    public boolean isSymmetricChild(TreeNode root1, TreeNode root2) {
        if (root1 == null && root2 == null) {
            return true;
        }
        if (root1 == null && root2 != null || root1 != null && root2 == null) {
            return false;
        }
        if (root1.val != root2.val) {
            return false;
        }
        return isSymmetricChild(root1.left, root2.right) && isSymmetricChild(root1.right, root2.left);
    }

    public boolean isSymmetric(TreeNode root) {
        if (root == null) {
            return true;
        }
        return isSymmetricChild(root.left, root.right);
    }

    //二叉数的分层排序
        public List<List<Integer>> levelOrder(TreeNode root) {
            if(root == null){
                return new ArrayList<List<Integer>>();
            }
            List<List<Integer>> list = new ArrayList<List<Integer>>();
            Queue<TreeNode> queue = new ArrayDeque();//创建队列
            queue.add(root);//添加根节点
            while(!queue.isEmpty()){
                int size = queue.size();//每个list该装有几个
                List<Integer> list1 = new ArrayList<>();
                while(size-->0){
                    TreeNode node = queue.poll();
                    list1.add(node.val);
                    if(node.left!=null){
                        queue.add(node.left);
                    }
                    if(node.right!=null){
                        queue.add(node.right);
                    }
                }
                list.add(list1);
            }
            return list;
        }

        //求两个节点的最近公共祖先
        public static TreeNode node;
    public TreeNode lowestCommonAncestor(TreeNode root, TreeNode p, TreeNode q) {
        if(root==null){
            return null;//递归结束条件
        }
        if(root==p||root==q){
            node = root;
            return node;
        }
        if(findNode(root.left,p,q)&&findNode(root.right,p,q)){
            node = root;
            return node;
        }
        lowestCommonAncestor(root.left,p,q);
        lowestCommonAncestor(root.right,p,q);
        return node;

    }
    public boolean findNode(TreeNode root,TreeNode p, TreeNode q){
        if(root == null){
            return false;
        }
        if(root == p||root == q){
            return true;
        }
        return findNode(root.left,p,q)||findNode(root.right,p,q);
    }

    //改良后的求两个节点的最近公共祖先
    public TreeNode lowestCommonAncestor2(TreeNode root, TreeNode p, TreeNode q) {
        if(root == null){
            return null;
        }
        if(root==p||root==q){
            return root;
        }
        TreeNode left = lowestCommonAncestor2(root.left,p,q);
        TreeNode right =lowestCommonAncestor2(root.right,p,q);
        if(left==null&&right==null) return null;
        if(left!=null&&right==null) return left;
        if(left==null&&right!=null) return right;
        return root;

    }

}